package dp;

/**
 * @author tmh
 * @date 2024/9/14 22:53
 * @description
 */
public class T63不同路径II {
    //这个题就是有障碍物的版本，有障碍物，说明不能到该位置，那么到该位置的走法就为0
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        //起点或者终点有障碍物，也不能到达目的地
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        //初始化第一行，如果第一行之间某个位置有障碍，那么障碍后面的位置是没有方法到的
        //对应的代码就是这个：i < n && obstacleGrid[0][i] == 0
        for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
                dp[0][i] = 1;
        }
        //初始化第一列 初始化的逻辑和上面一样
        for (int j = 0; j < m && obstacleGrid[j][0]==0; j++) {
                dp[j][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
